{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "e0c57b3a"
   },
   "source": [
    "##### Copyright 2020 The Cirq Developers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "id": "020331ec"
   },
   "outputs": [],
   "source": [
    "# @title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "# https://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "gross-longer"
   },
   "source": [
    "# Qubit Placement\n",
    "\n",
    "This notebooks walks through qubit placement runtime features exposed through the `cirq_google.workflow` tools."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "3609cf6b"
   },
   "source": [
    "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://quantumai.google/cirq/google/qubit-placement\"><img src=\"https://quantumai.google/site-assets/images/buttons/quantumai_logo_1x.png\" />View on QuantumAI</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/Cirq/blob/main/docs/google/qubit-placement.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/colab_logo_1x.png\" />Run in Google Colab</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://github.com/quantumlib/Cirq/blob/main/docs/google/qubit-placement.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/github_logo_1x.png\" />View source on GitHub</a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a href=\"https://storage.googleapis.com/tensorflow_docs/Cirq/docs/google/qubit-placement.ipynb\"><img src=\"https://quantumai.google/site-assets/images/buttons/download_icon_1x.png\" />Download notebook</a>\n",
    "  </td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "0f3974f5"
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    import cirq\n",
    "except ImportError:\n",
    "    print(\"installing cirq...\")\n",
    "    !pip install --quiet cirq\n",
    "    print(\"installed cirq.\")\n",
    "    import cirq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "subjective-sponsorship"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "sporting-inspector"
   },
   "source": [
    "## Target Device\n",
    "\n",
    "First, we get an example target device and---crucially---its qubit connectivity graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "acknowledged-declaration"
   },
   "outputs": [],
   "source": [
    "from cirq_google.workflow import SimulatedProcessorWithLocalDeviceRecord\n",
    "\n",
    "rainbow_record = SimulatedProcessorWithLocalDeviceRecord('rainbow')\n",
    "rainbow_device = rainbow_record.get_device()\n",
    "rainbow_graph = rainbow_device.metadata.nx_graph\n",
    "\n",
    "_ = cirq.draw_gridlike(rainbow_graph, tilted=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "roman-scanning"
   },
   "source": [
    "## Target problem topology\n",
    "\n",
    "We'll use a `NamedTopology` to talk about the graph connectivity of our circuit. In this case, we'll construct a random circuit on a `cirq.TiltedSquareLattice` topology of a given width and height."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "weighted-transaction"
   },
   "outputs": [],
   "source": [
    "topo = cirq.TiltedSquareLattice(3, 2)\n",
    "_ = cirq.draw_gridlike(topo.graph, tilted=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "northern-houston"
   },
   "outputs": [],
   "source": [
    "circuit = cirq.experiments.random_rotations_between_grid_interaction_layers_circuit(\n",
    "    qubits=sorted(topo.nodes_as_gridqubits()), depth=4\n",
    ")\n",
    "\n",
    "from cirq.contrib.svg import SVGCircuit\n",
    "\n",
    "SVGCircuit(circuit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "automated-entertainment"
   },
   "source": [
    "### Verify circuit connectivity\n",
    "\n",
    "We use a topology to generate a random circuit. Now we can extract the implied circuit topology from the two qubit gates within to verify that it is indeed the topology we requested:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "acting-disease"
   },
   "outputs": [],
   "source": [
    "from cirq.contrib.routing import get_circuit_connectivity\n",
    "\n",
    "circuit_graph = get_circuit_connectivity(circuit)\n",
    "_ = cirq.draw_gridlike(circuit_graph, tilted=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "banned-scotland"
   },
   "source": [
    "## QubitPlacer\n",
    "\n",
    "The following classes follow the `QubitPlacer` interface. In particular, there is a method `place_circuit` which maps arbitary input qubits in a circuit to qubits that exist on the device. It accepts a named problem topology and other runtime information to provide more context to the qubit placers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "objective-webcam"
   },
   "outputs": [],
   "source": [
    "# set up some other required arguments.\n",
    "# In a real `cirq_google.workflow.execute()` run, these will be\n",
    "# handled for you.\n",
    "\n",
    "from cirq_google.workflow import SharedRuntimeInfo\n",
    "\n",
    "shared_rt_info = SharedRuntimeInfo(run_id='example', device=rainbow_device)\n",
    "\n",
    "rs = np.random.RandomState(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "optical-express"
   },
   "source": [
    "## RandomDevicePlacer\n",
    "\n",
    "The `RandomDevicePlacer` will find random, valid placements. On a technical level, this uses networkx subgraph monomorphism routines to map the problem topology to the device graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "introductory-oxford"
   },
   "outputs": [],
   "source": [
    "from cirq_google.workflow import NaiveQubitPlacer, RandomDevicePlacer, HardcodedQubitPlacer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "outdoor-greeting"
   },
   "outputs": [],
   "source": [
    "rdp = RandomDevicePlacer()\n",
    "\n",
    "placed_c, placement = rdp.place_circuit(\n",
    "    circuit, problem_topology=topo, shared_rt_info=shared_rt_info, rs=rs\n",
    ")\n",
    "cirq.draw_placements(rainbow_graph, circuit_graph, [placement])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "drawn-apache"
   },
   "source": [
    "## NaiveQubitPlacer\n",
    "\n",
    "As a fallback, you can rely on `NaiveQubitPlacer` which will map input qubits to output qubits. Be careful though! This means you have to choose your qubits as part of circuit construction, which is not advised if you're using `cirq_google.workflow` best practices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "prepared-crisis"
   },
   "outputs": [],
   "source": [
    "naive = NaiveQubitPlacer()\n",
    "\n",
    "placed_c, placement = naive.place_circuit(\n",
    "    circuit, problem_topology=topo, shared_rt_info=shared_rt_info, rs=rs\n",
    ")\n",
    "cirq.draw_placements(rainbow_graph, circuit_graph, [placement])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "american-shelter"
   },
   "source": [
    "## HardcodedQubitPlacer\n",
    "\n",
    "If you want ultimate control over qubit placement but still want to decouple your `cg.QuantumExecutable`s from a particular device or configuration, you can use the `HardcodedQubitPlacer` to place your circuits at runtime but from a pre-specified list of valid placements.\n",
    "\n",
    "Here, we introduce a helper function to generate placements for all `TiltedSquareLattice` topologies anchored from qubit `(4, 2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "cardiovascular-review"
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "\n",
    "def all_offset_placements(device_graph, offset=(4, 2), min_sidelength=2, max_sidelength=5):\n",
    "    # Generate candidate tilted square lattice topologies\n",
    "    sidelens = list(itertools.product(range(min_sidelength, max_sidelength + 1), repeat=2))\n",
    "    topos = [cirq.TiltedSquareLattice(width, height) for width, height in sidelens]\n",
    "\n",
    "    # Make placements using TiltedSquareLattice.nodes_to_gridqubits offset parameter\n",
    "    placements = {topo: topo.nodes_to_gridqubits(offset=offset) for topo in topos}\n",
    "\n",
    "    # Only allow placements that are valid on the device graph\n",
    "    placements = {\n",
    "        topo: mapping\n",
    "        for topo, mapping in placements.items()\n",
    "        if cirq.is_valid_placement(device_graph, topo.graph, mapping)\n",
    "    }\n",
    "    return placements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "decimal-mississippi"
   },
   "source": [
    "The constructor for `HardcodedQubitPlacer` takes in a mapping from named topology to a \"placement\". Each placement is a mapping from named topology node to device qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "engaged-harbor"
   },
   "outputs": [],
   "source": [
    "rainbow_mapping = all_offset_placements(rainbow_graph)\n",
    "hardcoded = HardcodedQubitPlacer(mapping=rainbow_mapping)\n",
    "\n",
    "placed_c, placement = hardcoded.place_circuit(\n",
    "    circuit, problem_topology=topo, shared_rt_info=shared_rt_info, rs=rs\n",
    ")\n",
    "cirq.draw_placements(rainbow_graph, circuit_graph, [placement])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "foster-python"
   },
   "source": [
    "#### All hardcoded placements\n",
    "\n",
    "For completeness, the following figure shows all hardcoded placements. If you request one of the supported `TiltedSquareLattice` topology, you'll get the depicted mapping. If you request a topology not in the hardcoded list, you will receive an error. The `RandomDevicePlacer` (in contrast) will always succeed if the topology can be placed on the device."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "bizarre-extraction"
   },
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "n_col = 3\n",
    "n_row = int(ceil(len(rainbow_mapping) / n_col))\n",
    "fig, axes = plt.subplots(n_row, n_col, figsize=(4 * n_col, 3 * n_row))\n",
    "axes = axes.reshape(-1)\n",
    "for i, (topo, mapping) in enumerate(rainbow_mapping.items()):\n",
    "\n",
    "    axes[i].set_title(f'{topo.width}x{topo.height}')\n",
    "    cirq.draw_placements(rainbow_graph, topo.graph, [mapping], tilted=False, axes=axes[i : i + 1])\n",
    "\n",
    "fig.suptitle(\"All hardcoded placements\", fontsize=14)\n",
    "fig.tight_layout()"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "qubit-placement.ipynb",
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
